package datastructure.binarytree.sort;

/**
 * Created by hao on 17-3-23.
 */
public class MaxHeapSort {
    int[] heap;
    int heapSize;

    public MaxHeapSort(int[] array) {
        this.heap = array;
        this.heapSize = array.length; // 堆的大小不一定等于数组大小，有可能小于数组大小，heapSize表示有效数据的大小
    }

    /**
     * initialize a max heap
     */
    public void buildMaxHeap() {
        for (int i = heapSize/2 -1; i >= 0 ; i--) { //依次向上将当前子树最大堆化
            maxify(i);
//            printHeapTree(heap);
        }
    }

  /**
   * 堆排序
   */
  public void heapSort(){
        //执行n次，将每个当前最大的值放到堆末尾
        for (int i = 0; i < heap.length; i++) {
            int tmp = heap[0];
            heap[0] = heap[heapSize-1];
            heap[heapSize-1] = tmp;
            heapSize--;
            maxify(0);
        }
    }

    /**
     * 递归调整最大堆
     * @param rootIndex
     */
    public void maxify(int rootIndex) {
        int leftIndex = leftIndex(rootIndex);
        int rightIndex = rightIndex(rootIndex);
        int largestIndex;
        if (leftIndex < heapSize && heap[leftIndex] > heap[rootIndex]) {
            largestIndex = leftIndex;
        }else {
            largestIndex = rootIndex;
        }
        if (rightIndex < heapSize && heap[rightIndex] > heap[largestIndex]) {
            largestIndex = rightIndex;
        }
        if (largestIndex == rootIndex || largestIndex >= heapSize) {
          /**
           * 1. 第一个条件表示该父节点与两个子节点相比已经最大，满足堆性质，结束调整
           * 2. 第二个条件表示largest超出heap范围说明不存在比该父节点大的子女
           *    之所以要这样写是因为很多时候我们也可以用一个很长的数组（比如2n）来表示大小为n的堆。
           *    那样的话大于n以外的位置也可以存储数据，只是不是有效的数据
           */
            return;
        }
        //交换i与largest对应的元素位置，在largest位置递归调用maxify
        int tmp = heap[rootIndex];
        heap[rootIndex] = heap[largestIndex];
        heap[largestIndex] = tmp;
        maxify(largestIndex);
    }


    private int parentIndex(int n) {
        return (n-1) / 2;
    }

    private int leftIndex(int n) {
        return 2 * n +1;
    }

    private int rightIndex(int n) {
        return 2 * n + 2;
    }

    public static void printHeap(int[] heap) {
        for (int i = 0; i < heap.length; i++) {
            System.out.print(heap[i] + " ");
        }
      System.out.println();
    }
    
    public static void printHeapTree(int[] heap){
      for (int i = 1; i < heap.length; i*=2) { // i表示二叉树的当前高度
        for (int j = i - 1 ; j < (2 * i -1) && j < heap.length ; j++) {   //表示二叉树的当前节点的索引
          System.out.print(heap[j] + "  ");
        }
        System.out.println();
      }
      System.out.println();
    }

    public static void main(String[] args) {
        int[] array=new int[]{1,2,3,4,7,8,9,10,14,16};
        MaxHeapSort maxHeapSort = new MaxHeapSort(array);
        System.out.println("Original heap:");
        printHeap(maxHeapSort.heap);
      System.out.println("heap structure:");
      printHeapTree(maxHeapSort.heap);
        maxHeapSort.buildMaxHeap();
        System.out.println("After building max heap:");
      printHeap(maxHeapSort.heap);
      System.out.println("heap structure:");
      printHeapTree(maxHeapSort.heap);

        maxHeapSort.heapSort();
        System.out.println("After sorting:");
        printHeap(maxHeapSort.heap);

    }
}
